package data_structure.collection;

public class LinkedList<E> {
    private final Node<E> head = new Node<>(null);
    private int size;

    /**
     * 节点类
     *
     * @param <E>
     */
    private static class Node<E> {
        private E element;
        Node<E> next;

        public Node(E e) {
            this.element = e;
        }
    }

    /**
     * 添加元素
     *
     * @param element
     * @param index
     */
    public void add(E element, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("插入非法位置，合法的插入位置为：0 - " + index);
        }
        Node<E> prev = head;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node<E> node = new Node<>(element);
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    public E remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("删除非法位置，合法的删除位置为：0 - " + (index - 1));
        }
        Node<E> prev = head;
        for (int i = 0; i < index; i++) {
            // 找到前驱节点
            prev = prev.next;
        }
        // 先把待删除节点存放的元素取出来
        E element = prev.next.element;
        // 把下下节点覆盖至下节点
        prev.next = prev.next.next;
        size--;
        return element;
    }

    public E get(int index) {
        if (index < 0 || index > size - 1) {
            throw new IndexOutOfBoundsException("非法的位置，合法的位置为：0 - " + (index - 1));
        }
        Node<E> node = head;
        while (index-- >= 0) {
            node = node.next;
        }
        return node.element;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node<E> node = head.next;
        while (node != null) {
            // 从第一个节点开始，一个一个遍历，遍历一个就拼接到字符串上去
            builder.append(node.element).append(" ");
            node = node.next;
        }
        return builder.toString();
    }
}
